package leetcode.数学;

import java.util.ArrayList;
import java.util.List;

/**
 * 第 k 个排列
 *
 * 从小到大把数排好;
 *
 * 用backtrack的方法遍历,每次遍历到一个全排列那么结果,count+1;
 *
 * 遍历到n就return输出
 *
 * 由于用的是backtrack,后面 count > k的情况都直接return掉;
 */
public class Test60第k个排列 {

    static int count = 0;
    static List<Integer> finalRes;

    public static String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        //第几个解.
        List<Integer> resTemp = new ArrayList<>();
        boolean[] haveSeen = new boolean[n];
        backtrack(nums, k, resTemp, haveSeen);
        StringBuilder res = new StringBuilder();
        for (Integer i : finalRes) {
            res.append(i);
        }
        return res.toString();
    }

    public static void backtrack(int[] nums, int k,
                                 List<Integer> tempIndex,
                                 boolean[] haveSeen) {
        if (tempIndex.size() == nums.length) {
            count++;
        }
        if (count == k && tempIndex.size() == nums.length) {
            finalRes = new ArrayList<>(tempIndex);
            return;
        } else if (count < k && tempIndex.size() == nums.length) {
            tempIndex = new ArrayList<>();
        }
        for (int i = 0; i < nums.length; i++) {
            if (haveSeen[i]) {
                continue;
            }
            tempIndex.add(nums[i]);
            haveSeen[i] = true;
            backtrack(nums, k, tempIndex, haveSeen);
            haveSeen[i] = false;
            tempIndex.remove(tempIndex.size() - 1);
        }
    }

    public static void main(String[] args) {
        //伪代码
//        long startTime = System.currentTimeMillis();   //获取开始时间
//        System.out.println(getPermutation(4, 9));
//
//        long endTime = System.currentTimeMillis(); //获取结束时间
//        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");

        System.out.println(getPermutation2(8, 27));
    }


    /**
     * 逆康托展开算法：https://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/7968428
     * @param n 1-n 个数
     * @param k 第k个排列
     * @return 第k个排列是什么数
     */
    public static String getPermutation2(int n, int k) {
        // 构造 1 到 n 的数组
        int[] temp = new int[n];
        for (int i = 0; i < n; i++) {
            temp[i] = i + 1;
        }

        // 数组下标是从 0 开始，k 首先要减去 1
        k = k - 1;
        int factor = 0;
        StringBuffer ans = new StringBuffer();
        for (int i = 0; i < n; i++) {
            factor = factor(n - i - 1);
            ans.append(temp[k / factor]);
            del(temp, n - i, k / factor);
            k = k % factor;
        }
        return ans.toString();
    }

    // 求 n!
    public static int factor(int n) {
        int num = 1;
        while (n > 0) {
            num = num * (n--);
        }
        return num;
    }

    // 删除数组中第 k 个元素
    public static void del(int[] num, int length, int k) {
        while (k < length - 1) {
            num[k] = num[k + 1];
            k++;
        }

    }
}
